COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	block.not[f83,jmc]	Notes on programs for building towers
C00007 ENDMK
C⊗;
block.not[f83,jmc]	Notes on programs for building towers

	We will use the blocks world as a vehicle for some ideas
about programming in general, AI programming in particular, about
formalization of knowledge, and about reasoning programs.

	We consider various programs for building structures
consisting of towers of blocks.  A typical problem begins with
a structure  ((A B) (C)) representing a situation with block
A on block B, block B on the table and block C on the table.
Our goal is to compute the moves required to build another
structure out of the same blocks.  For example,  ((A B C))
represents a tower with A on B, B on C and C on the table.
The solution is a sequence of moves, for example,
((A Table) (B C) (A B)).  Usually it is convenient to compute
the moves in reverse order, so we shall usually write
((A B) (B C) (A Table)) instead.

	There seems to be a conflict between opportunism and
planning.  Some of our programs for building structures proceed
systematically building one at a time the towers of the final
desired structure.  Such a program builds each tower from the
bottom up, taking into account the fact that to move a block
both it and its destination must be clear.  Any blocks that
must be moved to clear a block are in general moved to the
table, though some programs will move them to their final
destinations when this is possible.   However, it is often
possible to build the structure in fewer moves by proceeding
opportunistically.  First of all, any block that can be moved
to its final destination where all the blocks below it in the
desired tower are in place should be so moved.  Secondly, if
a block is not in its final position but is above blocks
that will be below it, then it might as well be moved to the
table right away, since it will have to be moved to the table
eventually.  Making such opportunistic moves often simplifies
the construction problem.  However, it seems that such moves
disrupt a plan that is being carried out, not in the sense
of making its goals harder to achieve, but in the sense of
putting the situation into a state not contemplated in the
plan.  We will study how to reconcile these desiderata.

1983 Nov 21

How can we formulate as a sentence of first order logic the
proposition that towers must be built from the bottom up.
Note that its proof depends on the fact that there are as
many spaces on the table as may be required.

bad(move,s,g) ≡ distance(update(move,s),g) ≥ distance(s,g)

dest(move,s) ≠ table ∧ ¬to-final(move,s,g) ⊃ bad(move,s,g)

The proof is based on the fact that for any sequence of moves
from update(move,s)  that achieves  g, there is a corresponding
sequence of moves from  s  that achieves  g  and is shorter.

1983 Dec 22

Consider a pattern matching program that finds deadlocked sets
of blocks that cannot be put into their final position without
putting some blocks on the table.  The simplest such pattern is
a cycle.  (Moving A requires moving B which requires moving C
which requires moving A).  However, if moving a block requires
moving two blocks, there may be more complicated patterns than
cycles.